from typing import List

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        m, n = len(nums1), len(nums2)
        max_num = []
        
        # 枚举从nums1中取i个数字的所有可能，i的范围为max(0, k-n)到min(m, k)
        for i in range(max(0, k - n), min(m, k) + 1):
            # 从nums1中取出i个数字组成的最大数
            sub1 = self.maxSubsequence(nums1, i)
            # 从nums2中取出k-i个数字组成的最大数
            sub2 = self.maxSubsequence(nums2, k - i)
            # 合并两个子序列得到当前组合的最大数
            merged = self.merge(sub1, sub2)
            # 更新全局最大数
            if merged > max_num:
                max_num = merged
        
        return max_num
    
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        """从数组中取出k个数字，保持相对顺序不变，组成最大数"""
        stack = []
        n = len(nums)
        to_pop = n - k  # 需要移除的数字个数
        
        for num in nums:
            # 当栈不为空，当前数字大于栈顶，且还有数字可以移除时，弹出栈顶
            while stack and num > stack[-1] and to_pop > 0:
                stack.pop()
                to_pop -= 1
            stack.append(num)
        
        # 如果还有剩余的数字需要移除，从尾部移除
        while to_pop > 0:
            stack.pop()
            to_pop -= 1
        
        return stack
    
    def merge(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """合并两个数组，保持相对顺序不变，得到字典序最大的合并结果"""
        merged = []
        i = j = 0
        
        while i < len(nums1) or j < len(nums2):
            if nums1[i:] > nums2[j:]:
                merged.append(nums1[i])
                i += 1
            else:
                merged.append(nums2[j])
                j += 1
        
        return merged    